//我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。 
//
// 
//
// 示例: 
//
// 输入: n = 10
//输出: 12
//解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 
//
// 说明: 
//
// 
// 1 是丑数。 
// n 不超过1690。 
// 
//
// 注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/ 
// Related Topics 哈希表 数学 动态规划 堆（优先队列） 👍 274 👎 0

package com.cute.leetcode.editor.cn;

import java.util.*;

public class ChouShuLcof {
    public static void main(String[] args) {
        new ChouShuLcof().new Solution().nthUglyNumber(20);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 需要将已经求出的丑数进行保存
         * 使用list的话由于每次都需要遍历，时间复杂度太高
         */
        public int nthUglyNumber1(int n) {
            List<Integer> list = new ArrayList<>();
            list.add(0);list.add(1);
            int index = 1;
            // 因为后边的数求出的丑数可能要小于前边的数求出的丑数，终止条件成了一个问题
            while (index < list.size()){
                int num = list.get(index++);
                if (!list.contains(num * 2) && num < Integer.MAX_VALUE / 2) list.add(num * 2);
                if (!list.contains(num * 3) && num < Integer.MAX_VALUE / 3) list.add(num * 3);
                if (!list.contains(num * 5) && num < Integer.MAX_VALUE / 5) list.add(num * 5);
                Collections.sort(list);
            }
            return list.get(n);
        }

        /**
         * 以下题解和剑指Offer书上和leetcode上的题解是一致的思路
         * 使用dp来做
         * dp[i]表示n-1位置的丑数,dp[0] = 1
         * 求dp[i]的时候，理论上是需要取得前边所有丑数的 2 3 5倍中第一个 > dp[i-1]的值
         * 如果每次计算所有值的话时间上略显复杂，所以有如下分析：
         * 而且数组中对于2倍而言，一定有一个位置a存在，使得其前边的丑数 * 2 < dp[i-1],后边的数*2 > dp[i-1]
         * 对于3倍5倍而言同样存在bc两个位置
         * 所以每次求解dp[i]时只需要计算dp[a]*2,dp[b]*3,dp[c]*5然后取得其最小值即可
         * 再对abc三个位置根据条件进行更新
         */
        public int nthUglyNumber(int n) {
            int[] dp = new int[n];
            dp[0] = 1;
            int a = 0, b = 0, c = 0;
            for (int i = 1; i < n; i++) {
                int num1 = dp[a] * 2, num2 = dp[b] * 3, num3 = dp[c] * 5;
                dp[i] = Math.min(Math.min(num1, num2), num3);
                if (dp[i] == num1) a++;
                if (dp[i] == num2) b++;
                if (dp[i] == num3) c++;
            }
            return dp[n-1];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}